#include <iostream>
#include <vector>
using namespace std;

/**
 * 
 * 给定一个含有 n 个正整数的数组和一个正整数 target 。
 * 找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
 *  
 * 示例 1：
 * 输入：target = 7, nums = [2,3,1,2,4,3]
 * 输出：2
 * 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
 * 
 * 示例 2：
 * 输入：target = 4, nums = [1,4,4]
 * 输出：1
 * 
 * 示例 3：
 * 输入：target = 11, nums = [1,1,1,1,1,1,1,1]
 * 输出：0
 * 
 * 思路：此题有两种思路
 * 一种为暴力求解，直接运用for循环的嵌套遍历所有的情况寻找最优解
 * 
 * 另一种为使用滑动窗口，通过移动定义的start和end指针来一点点缩小范围
 * 直到找到最优解停止
 * 
 * 
 *  
 */

//第一种方法的具体实现
class Solution_1 {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }
        int ans = __INT_MAX__;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += nums[j];
                if (sum >= s) {
                    ans = min(ans, j - i + 1);
                    break;
                }
            }
        }
        return ans == __INT_MAX__ ? 0 : ans;
    }
};

//第二种方法的具体实现
class Solution_2 {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        //此处对特殊情况做了一个判断，即数组为空子数组也为空
        if(n == 0) {
            return 0;
        }
        //在开始默认子数组无穷大
        int ans = __INT_MAX__;
        
        //定义滑动窗口的两个指针
        int start = 0;
        int end = 0;
        int sum = 0;

        //整个滑动窗口存在的情况为end指针在规定的范围之内
        while(end < n) {
            sum += nums[end];
            //首先确定满足条件的一个子数组范围，随后运用滑动窗口查找其中最先的子数组范围
            while(sum >= target) {
                ans = min(ans, end - start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return ans == __INT_MAX__ ? 0 : ans;
    }
};

int main()
{
    Solution_1 problem1;
    int target_1 = 7;
    vector<int> nums_1 = {2,3,1,2,4,3};
    cout << problem1.minSubArrayLen(target_1, nums_1) << endl;

    Solution_2 problem2;
    int target_2 = 4;
    vector<int> nums_2 = {1, 4, 4};
    cout << problem2.minSubArrayLen(target_2, nums_2) << endl;
    return 0;
}